/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

public class LexiconTrie implements LexiconInterface
{
	private Trie prefixTree;

	/**
	 * Load the words from an input source and store them in this lexicon.
	 * 
	 * @param input
	 *            A scanner that will provide the entire dictionary.
	 */
	public void load(Scanner input)
	{
		prefixTree = new Trie();

		while (input.hasNext())
		{
			prefixTree.addWord(input.next().toLowerCase());
		}
	}

	/**
	 * If the prefix is in the lexicon, returns true.
	 * 
	 * @param s
	 *            The prefix to search for.
	 * @return True if the lexicon contains a word that has prefix s.
	 */
	public boolean containsPrefix(String s)
	{
		return prefixTree.containsPrefix(s.toLowerCase());
	}

	/**
	 * If the word is in the lexicon, returns true.
	 * 
	 * @param s
	 *            The word to search for.
	 * @return True if the lexicon contains s.
	 */
	public boolean contains(String s)
	{
		return prefixTree.containsWord(s.toLowerCase());
	}

	/**
	 * Overridden toString method, implemented for testing convenience. See TrieNode.toString() for details.
	 * 
	 * @return The string that represents this LexiconTrie.
	 */
	public String toString()
	{
		return prefixTree.toString();
	}

	/**
	 * Prints this.toString() to System.out.
	 */
	public void print() // added for convenience
	{
		System.out.println(toString());
	}

	/**
	 * Creates and returns a new TrieIterator used for iterating over the LexiconTrie
	 */
	@Override
	public Iterator<String> iterator()
	{
		return prefixTree.iterator();
	}

	// Trie class definition
	// wrapper class for TrieNode that is technically unnecessary, but allows
	// proper encapsulation and better abstraction
	private class Trie
	{
		public static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz";
		private TrieNode root;

		/**
		 * Sole constructor for Trie, simply initializes root TrieNode
		 */
		private Trie()
		{
			root = new TrieNode();
		}

		/**
		 * Adds word to the Trie, marking it's end point so it can be found explicitly with containsWord.
		 * 
		 * @param word
		 *            The string to add.
		 */
		private void addWord(String word)
		{
			if (word.length() != 0)
			{
				root.add(word, 0);
			}
		}

		/**
		 * Tests whether the word word is contained in this Trie. Word is only contained if final character in Trie specifically ends a word.
		 * 
		 * @param word
		 *            The word to look for.
		 * @return True if word is found.
		 */
		private boolean containsWord(String word)
		{
			if (word.length() == 0)
			{
				return false;
			}

			return root.contains(word, 0, true);
		}

		/**
		 * Tests whether the prefix pre is contained in this Trie. Prefix is contained regardless of whether final character of pre in Trie ends a word or not.
		 * 
		 * @param pre
		 *            The prefix to look for.
		 * @return True if pre is found.
		 */
		private boolean containsPrefix(String pre)
		{
			if (pre.length() == 0)
			{
				return true;
			}

			return root.contains(pre, 0, false);
		}

		/**
		 * Overridden toString method, implemented for testing convenience. See TrieNode.toString() for details.
		 * 
		 * @return The string that represents this Trie.
		 */
		public String toString()
		{
			return root.toString();
		}

		/**
		 * Makes and returns iterator object for looping over words in trie
		 */
		private Iterator<String> iterator()
		{
			return new TrieIterator(this);
		}

		// TrieIterator class definition, iterator is alphabetical
		public class TrieIterator implements Iterator<String>
		{
			private Stack<TrieNode> roots;
			private Stack<Integer> indices;
			private String curWord;

			/**
			 * Makes a trie iterator from this Trie object
			 */
			private TrieIterator(Trie t)
			{
				roots = new Stack<TrieNode>();
				roots.push(t.root);
				indices = new Stack<Integer>();
				indices.push(0);
				curWord = "";
				advanceWord();
			}

			/**
			 * returns true when iterator has more values
			 */
			public boolean hasNext()
			{
				return !roots.isEmpty();
			}

			/**
			 * returns next iterator value
			 */
			public String next()
			{
				return advanceWord();
			}

			/**
			 * required but unused iterator remove method
			 */
			public void remove()
			{
				// unused, not implemented
			}

			/**
			 * advances curWord to the next word in the Trie
			 */
			private String advanceWord()
			{
				// add chars to
				TrieNode r = roots.peek();
				int i = indices.peek();

				String returnWord = curWord;

				for (int j = i; j != ALPHABET.length(); j++)
				{

					r = roots.peek();
					if (r.suffixes != null && r.suffixes[j] != null) // if child found
					{
						roots.push(r.suffixes[j]); // add child node to stack
						indices.pop(); //replace top index with index after child just found
						indices.push(j);
						indices.push(0); // add 0 that corresponds with child just pushed to roots

						curWord += ALPHABET.charAt(j); // add character of found child to word
						
						if (r.suffixes[j].endsWord) // stop if node found ends a word
						{
							break;
						}

						// otherwise, reset values to so looping can continue

						j = -1;
						i = 0;
					} else if (j == ALPHABET.length() - 1)
					{
						indices.pop();
						if (indices.isEmpty())
						{
							indices.push(0);
						}
						i = indices.peek();
						j = i;
						roots.pop();
						if (roots.isEmpty())
						{
							break;
						}
						r = roots.peek();
						curWord = curWord.substring(0, curWord.length() - 1);
					}
				}
				return returnWord;
			}
		}

		// TrieNode class definition
		private class TrieNode
		{
			private boolean endsWord; // initially false
			private TrieNode[] suffixes; // initially null

			/**
			 * Adds portion of word after and including index index to this TrieNode. Marks the last character added as the end of a word.
			 * 
			 * @param word
			 *            String to add.
			 * @param index
			 *            Location in word to start adding from.
			 */
			private void add(String word, int index)
			{
				int i = Trie.ALPHABET.indexOf(word.charAt(index));

				if (i == -1) // ensure character in word is valid
				{
					throw new IllegalArgumentException("Illegal character found.");
				}

				if (suffixes == null)
				{
					suffixes = new TrieNode[Trie.ALPHABET.length()];
				}

				if (suffixes[i] == null)
				{
					suffixes[i] = new TrieNode();
				}

				if (index + 1 == word.length()) // if done adding word
				{
					suffixes[i].endsWord = true; // mark last node as end of
													// word
				} else
				{
					suffixes[i].add(word, index + 1); // otherwise, continue
														// adding word
				}
			}

			/**
			 * Checks whether the string s after and including index index is present in this TrieNode. If isWord is true, only strings explicitly marked as the end of words return true. Otherwise a prefix is searched for, which is regardless of word endings.
			 * 
			 * @param word
			 *            String to add.
			 * @param index
			 *            Location in s to start containment search.
			 * @param isWord
			 *            Determines if only proper word (not merely prefixes) must be found.
			 * @return True if s is found to be contained in this TrieNode.
			 */
			private boolean contains(String s, int index, boolean isWord)
			{
				// return failure if end of word not reached and there are no
				// more branches to look at
				if (suffixes == null)
				{
					return false;
				}

				int i = Trie.ALPHABET.indexOf(s.charAt(index));

				if (i == -1) // ensure character in s is valid
				{
					throw new IllegalArgumentException("Illegal character found.");
				}

				if (suffixes[i] == null)
				{
					return false;
				}

				if (index + 1 == s.length()) // if end of s reached
				{
					if (isWord)
					{
						return suffixes[i].endsWord;
					}

					return true;
				}

				return suffixes[i].contains(s, index + 1, isWord);
			}

			/**
			 * Overridden toString method, implemented for testing convenience. Recursively writes TrieNode and all contents: - prints alphabet letters corresponding to non-null indices of this TrieNode's suffixes array - after each letter, the contents of suffixes at that letter index is printed in brackets - if that index of suffixes is an empty TrieNode, no brackets are printed (resulting in only the letter) - capital letter indicates the end of a word
			 * 
			 * e.g., adding words "rat", "race", "ram", and "rim" should result in "r[a[c[E]MT]i[M]]" (interestingly, the alphabetically first word added can be read from the front of the result, e.g. "r[a[c[E")
			 * 
			 * @return The string that represents this rieNode, see above for details.
			 */
			public String toString()
			{
				if (suffixes == null)
				{
					return "";
				}

				String s = "";

				for (int i = 0; i != suffixes.length; i++)
				{
					if (suffixes[i] != null)
					{
						if (suffixes[i].endsWord)
						{
							s += Character.toUpperCase(Trie.ALPHABET.charAt(i));
						} else
						{
							s += Trie.ALPHABET.charAt(i);
						}

						String s2 = suffixes[i].toString();

						if (s2.length() != 0)
						{
							s += "[" + suffixes[i].toString() + "]";
						}
					}
				}

				return s;
			}
		}
	}
}